/*
 * Copyright (C) 2021 VIPKID, Inc. All Rights Reserved.
 */
package cn.yuemouren.suanfa;

import java.util.LinkedList;

/**
 * <p>
 * 拓扑排序(可用来根据单一顺序推断出整体顺序、也可以用来检测是否存在环)
 * </p>
 *
 * @author timi
 * @date 2021/5/17 上午10:19
 **/
public class TopologicalSort {

    private LinkedList<Integer>[] adj;

    public TopologicalSort(LinkedList<Integer>[] adj) {
        this.adj = adj;
    }

    public LinkedList<Integer>[] getLinked(int v) {
        LinkedList[] lists = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<Integer>();
        }
        return lists;
    }

    /**
     * Kahn算法
     */
    public void sort1() {
        //统计入度数量
        Integer[] nums = new Integer[adj.length];
        for (LinkedList<Integer> list : adj) {
            for (Integer i : list) {
                nums[i]++;
            }
        }

        //可以输出的集合
        LinkedList<Integer> queue = new LinkedList<>();

        //入度为零的证明不需要依赖其他，可以先加入到返回值中
        for (int i = 0; i < adj.length; i++) {
            if (nums[i] == 0) {
                queue.add(i);
            }
        }

        //剩下处理入度不为零的
        while (!queue.isEmpty()) {
            Integer i = queue.removeFirst();
            System.out.print(i + "->");
            for (int j = 0; i < adj[i].size(); j++) {
                Integer num = adj[i].get(j);
                nums[num]--;
                if (nums[num] == 0) {
                    queue.add(num);
                }
            }
        }
    }

    /**
     * DFS算法
     */
    public void sort2() {
        int length = adj.length;
        //构建逆序列
        LinkedList<Integer>[] ada = getLinked(length);
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                Integer w = adj[i].get(j);
                ada[w].add(i);
            }
        }

        //遍历过的节点记录，放置重复遍历
        boolean[] visited = new boolean[length];
        for (int i = 0; i < length; i++) {
            if (!visited[i]) {
                visited[i] = true;
            }
        }

    }

    /**
     * 深度优先遍历
     *
     * @param i       当前值
     * @param ada     逆序列
     * @param visited 遍历数记录
     */
    private void dfs(int i, LinkedList<Integer>[] ada, boolean[] visited) {

        for (int j = 0; j < ada[i].size(); j++) {
            Integer w = ada[i].get(j);
            if (visited[w]) {
                continue;
            }
            visited[w] = true;
            dfs(i, ada, visited);
        }
        System.out.println(i + "->");
    }
}
